Problem statement: zenit17skf

Františkove čísla

Počet bodov: 30, časový limit: 1000ms

Každý matematický frajer má po sebe niečo pomenované. Okrem Františka. Až dodnes – uvádzame úžasné Františkove čísla! Celé číslo \(n\) sa nazýva Františkovým, ak ho vieme zapísať v tvare \(n = x^y\), kde \(2 \leq x,y\), alebo ako súčet ľubovoľne veľa menších Františkovych čísel. Teda napríklad \(50\) je Františkovým číslom, pretože \(50 = 25 + 25\), pričom \(25 = 5^2\) je Františkovým číslom.

Predtým, ako túto slávnostnú udalosť oznámime Františkovi, chceli by sme o jeho číslach pozbierať nejaké pôsobivé štatistiky. Na začiatok napríklad, aké časté sú! Máme zopár intervalov čísel, ktoré sú v elitných matematických kluboch vysoko uznávané. Pomôžte nám zistiť, koľko čísel z nich je Františkových.

Vstup a výstup

V prvom riadku je celé číslo \(q\) – počet intervalov, ktoré nás zaujímajú. Nasleduje \(q\) riadkov, v každom z nich dve čísla \(a \leq b\), reprezentujúce jeden zaujímavý interval.

Pre každý interval \(a,b\) vypíšte, koľko čísel medzi \(a\) a \(b\) vrátane, je Františkových.

Je šesť vstupov. V prvých troch \(b\) neprekročí \(3\,000\), v druhých troch \(10^{18}\). Pre obe skupinky vstupov je \(q\) postupne najviac \(20, 10^3, 10^5\).

 Príklad

Input:

2
2 10
47 47

Output:

3
1

V intervale [2,10] sú Františkove čísla \(2^2 = 4\), \(2^3 = 8\), a \(3^2 = 9\). V druhej otázke vieme \(47\) zapísať ako \(5^2 + 3^2 + 3^2 + 2^2\).